import java.util.Arrays;

/**
 * 基数排序
 * 思路：个位数字排序 -> 十位数字排序 -> 百位数字排序 -> ...
 *
 * 如何获取一个数的个位，百位，千位
 * 以 9876 为例：
 * 取个位：9876 % 10 = 6，6 / 1 = 6
 * 取十位：9876 % 100 = 76，76 / 10 = 7
 * 取百位：9876 % 1000 = 876，876 / 100 = 8
 * 取千位：9876 % 10000 = 9876，9876 / 1000 = 9
 *
 * 关键：bucket 的数量（20 个）
 * 不论是个位、十位、百位还是千位上，只能用 [0, 9] 中的 10 个数字来表示
 * 所以桶的数量，用 20 个就够了（正数 10 个，负数 10 个）
 */
public class RadixSort {
    public static int[] radixSort(int[] nums) {
        int[] res = Arrays.copyOf(nums, nums.length);
        int len = nums.length;
        int maxDigit = getMaxDigit(res);
        int mod = 10, divide = 1;

        // 有多少位，就遍历几次
        for (int i = 0; i < maxDigit; i++) {
            int[][] counter = new int[20][0];
            for (int j = 0; j < len; j++) {
                int bucket = (res[j] % mod) / divide;
                // bucket 可能为负数
                bucket += 10;
                // 元素 res[j] 放入桶中
                counter[bucket] = enlargeBucket(counter[bucket], res[j]);
            }
            int idx = 0;
            // 从桶中取元素，重新赋值到 res 数组中
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    res[idx ++] = value;
                }
            }
            // 个位 -> 十位 -> 百位 -> ...
            mod *= 10;
            divide *= 10;
        }
        return res;
    }

    /**
     * 实现桶扩容
     * 1. 数组扩容一个单位
     * 2. 在扩容的位置上，添加元素 val（扩容单位在数组末尾，即添加元素到数组末尾）
     * 3. 返回新数组
     */
    public static int[] enlargeBucket(int[] arr, int val) {
        int[] newArr = Arrays.copyOf(arr, arr.length + 1);
        newArr[newArr.length - 1] = val;
        return newArr;
    }

    /**
     * 获得 nums 中最大的绝对值有多少位
     */
    public static int getMaxDigit(int[] nums) {
        // 最大的绝对值
        int maxVal = Math.abs(nums[0]);
        for (int num : nums) {
            // 一定要取绝对值，否则 {-10, 1} 的最大值为 1
            maxVal = Math.max(maxVal, Math.abs(num));
        }
        int cnt = 0;
        // 2.最大值有多少位
        while (maxVal != 0) {
            maxVal /= 10;
            cnt ++;
        }
        return cnt;
    }
}
